package com.dy.分类.数组._128_最长连续序列;

import java.util.HashMap;

/*
_128_最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
 */
public class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num :nums){
            if(!map.containsKey(num)){
                int left = map.getOrDefault(num-1,0);
                int right = map.getOrDefault(num+1,0);
                int len = left+right+1;
                map.put(num,len);
                res = Math.max(res,len);
                if(left!=0) map.put(num-left,len);
                if(right!=0) map.put(num+right,len);

            }
        }
        return res;
    }
    //复习
    public int longestConsecutive2(int[] nums) {
        int res =0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(!map.containsKey(nums[i])){
                int leftLen = map.getOrDefault(nums[i]-1,0);
                int rightLen = map.getOrDefault(nums[i]+1,0);
                int len = leftLen+1+rightLen;
                map.put(nums[i],len);
                res = Math.max(len,res);
                if(leftLen!=0) map.put(nums[i]-leftLen,len);
                if(rightLen!=0) map.put(nums[i]+rightLen,len);
            }
        }
        return res;
    }
}
